class Solution 
{
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries)
    {
        // Step 1：对各节点进行编号
        int nvars = 0;
        unordered_map<string, int> variables;
        for (size_t i = 0; i < equations.size(); i++)
        {
            if (variables.find(equations[i][0]) == variables.end())
            {
                variables[equations[i][0]] = nvars++;
            }
            if (variables.find(equations[i][1]) == variables.end())
            {
                variables[equations[i][1]] = nvars++;
            }
        }

        // Step 2：构建带权重的有向图
        vector<vector<pair<int, double>>> edges(nvars);
        for (size_t i = 0; i < equations.size(); i++)
        {
            int va = variables[equations[i][0]], vb = variables[equations[i][1]];
            edges[va].push_back(make_pair(vb, values[i]));
            edges[vb].push_back(make_pair(va, 1 / values[i]));
        }

        // Step 3：广度优先搜索有向图，寻找解
        vector<double> ret;
        for (size_t i = 0; i < queries.size(); i++)
        {
            double result = -1.0;
            if (variables.find(queries[i][0]) != variables.end() && variables.find(queries[i][1]) != variables.end())   // 计算值均存在于有向图中
            {
                int ia = variables[queries[i][0]], ib = variables[queries[i][1]];
                if (ia == ib)
                {
                    result = 1.0;
                }
                else
                {
                    queue<int> points;
                    points.push(ia);

                    vector<double> ratios(nvars, -1.0);                 // 从节点ia出发，到达节点ib的权重乘积
                    ratios[ia] = 1.0;

                    while (!points.empty() && ratios[ib] < 0)           // 广度搜索的终止条件，找到节点ib或队列为空
                    {
                        int x = points.front();
                        points.pop();

                        for (size_t i = 0; i < edges[x].size(); i++)    // 所有同节点x相邻的边
                        {
                            if (ratios[edges[x][i].first] < 0)          // 当前节点尚未被访问过
                            {
                                ratios[edges[x][i].first] = ratios[x] * edges[x][i].second;
                                points.push(edges[x][i].first);
                            }
                        }
                    }
                    result = ratios[ib];
                }
            }
            ret.push_back(result);
        }
        return ret;
    }
};